#GOAL: take set of k unique=distinct random numbers from interval [0..n)

#linear time O(n)
#based on Fisher-Yates or Reservoir sampling
def rand_set1(k, n)
  ret = Array.new(k) {k}
  n.times do |i|
    j = rand(i + 1) #in range [0;i]
    ret[j] = i if j < k
  end
  ret
end

#should be close to linear of k: O(k) if Set lookup is constant
#based on Richard Floyd sampling algorithm
require 'set'
def rand_set2(k, n)
  ret = Set.new
  (n-k..n-1).each do |i|
    j = rand(i + 1) #in range [0;i]
    if not ret.include? j
      ret << j
    else
      ret << i
    end
  end
  ret
end


def shuffle(arr)
  (0..arr.size-1).each do |i|
    j = rand(i+1) # in range [0;i]
    arr[j], arr[i] = arr[i], arr[j] #swapping
  end
  arr
end

#p shuffle((1..10).to_a)

#now benchmarking!
require 'benchmark'
tests = []
tests << {:k => 10, :n => 10000}
tests << {:k => 10, :n => 1000000}
#tests << {:k => 10, :n => 10000000}

#tests << {:k => 1000, :n => 10000000}
tests << {:k => 100000, :n => 10000000}
tests << {:k => 1000000, :n => 10000000}
tests << {:k => 10000000, :n => 10000000}
  
  
tests.each do |test|
  puts "Test #{tests.index(test) + 1}"
  string = "K = #{test[:k]} \t N = #{test[:n]} \n"
  string += "Reservoir sampling = "
  string += Benchmark.realtime {rand_set1(test[:k], test[:n])}.to_s
  string += "\t Floyd sampling = "
  string += Benchmark.realtime {rand_set2(test[:k], test[:n])}.to_s
  string += "\n---------------------------------------------------------------------------\n\n"
  puts string
end

#conclusion: Floyd sampling RULES!: generally outperforms reservoir sampling significantly, if N (the boundaries of random numbers) are known in advance


